# 给你两个字符串 haystack 和 needle ，
# 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
# 如果 needle 不是 haystack 的一部分，则返回   - 1 。

# KMP算法
class Solution:
    # next数组生成函数，递推求解最长公共前后缀
    # ADAAAAHDHDHLSKALK
    def next_build(self, rna: str) -> list:
        next_array = [0]
        i = 1
        prefix_len = 0
        while i < len(rna):
            if rna[prefix_len] == rna[i]:
                prefix_len += 1
                next_array.append(prefix_len)
                i += 1
            else:
                if prefix_len == 0:
                    next_array.append(0)
                    i += 1
                else:
                    prefix_len = next_array[i-1]
        return next_array
    # KMP主算法
    def strStr(self, dna: str, rna: str) -> int:
        next_array = self.next_build(rna)
        d, r = 0, 0               # 创建next数组，初始化索引、指针，获取字符串长度
        dnalen, rnalen = len(dna), len(rna)
        flag = False              # 若循环后flag仍为False则主串不包含子串
        while d < dnalen:         # 不能将and r < len(rna)写到这里，因为r=len(rna)时说明匹配成功，要用于判断并返回结果
            if dna[d] == rna[r]:  # 分字符匹配与失配两种情况，r取值：r=0 0<r<len(rna) r=len(rna)
                d += 1            # 字符匹配：如果主串字符与子串字符相同则比较下一个字符
                r += 1
            elif r > 0:           # 字符失配：不同则查询next数组，排除首字符失配的情况
                r = next_array[r-1]
            else:                 # 首字符失配，dna[0] != rna[0]，如果写到第一条会增加不必要的比较次数
                d += 1
            if r == rnalen:       # 字符串匹配成功，需新建一个if执行判断
                flag = True       # 此时为执行：if dna[d] == rna[r]: d++, r++;后，且r=len(rna)、d为后一位字符下标索引
                return d-rnalen   # 主串包含子串，返回主串中匹配子串的首字符索引（d-r不减1）
        if flag == False:         # 主串不包含子串，返回-1
            return -1
            

# 暴力算法
class Solution:
    def strStr(self, dna: str, rna: str) -> int:
        flag = False
        for i in range(len(dna)):
            if rna == dna[i:i+len(rna)]:
                flag = True
                return i
        if flag == False:
            return -1

# 作弊算法
# class Solution:
#     def strStr(self, haystack: str, needle: str) -> int:
#         if not needle:
#             return 0
#         return haystack.find(needle)

class A:
    def funcA(self, b):
        b += 1
        print('funcA:',b)
        return b
    def funcB(self, a, b):
        print('funcB',a,b)
        next = a + self.funcA(b)
        print('funcB',next)
        return next
dna = 1
rna = 0
test = A()
test.funcB(dna,rna)
